package airthmetic.exercise.dp;

public class _213_打家劫舍II {

    public static int rob(int[] nums) {
        /**
         动态规划思考问题
         1.确认状态参数和选择
         状态参数：下标

         选择/决策：选择不同的下标

         2.定义dp table的含义
         int[] dp = new int[];
         dp[i]表示第i间房子最多能偷取金额

         3.初始化 dp table
         因为求解问题i 依赖于i+1 和i+2 ,所以是从n~0遍历并且初始化 i+1 i+2为0

         4.推导状态转移公式
         dp[i] 偷 dp[i+2] + nums[i]
         不偷 dp[i+1]


         */
        int m = nums.length;
        if(m == 1){
            return nums[0];
        }
        return Math.max(dp(0,m-2,nums), dp(1,m-1,nums));
    }


    public static int dp(int left, int right, int[] nums){
        int dp_0 = 0;
        int dp_0_1 = 0;
        int dp_0_2 = 0;

        for(int i=right; i>=left; i--){
            dp_0 = Math.max(dp_0_1, nums[i] + dp_0_2);
            dp_0_2 = dp_0_1;
            dp_0_1 = dp_0;
        }

        return dp_0;
    }


    public static void main(String[] args) {
//        System.out.println(rob(new int[]{2,3,2}));
        System.out.println(rob(new int[]{1,2}));
        System.out.println(rob(new int[]{3}));
    }



}
